The quality of network security situational element extraction plays a crucial role in network security situation assessment. However, most of the existing network security situational element extraction methods rely on prior knowledge, and are not suitable for processing network security situational data. For effective and accurate extraction of network security situational elements, a parallel reduction algorithm based on matrix of attribute importance was proposed. The parallel reduction was introduced into classical rough set, then a single decision information table was expanded to multiple ones without affecting the classification. The conditional entropy was used to calculate attribute importance, and the redundant attributes were deleted according to reduction rules, thus the network security situational elements were extracted efficiently. In order to verify the efficiency of the proposed algorithm, the classification prediction was implemented on Weka. Compared with the usage of all the attributes, the classification modeling time on NSL-KDD dataset was reduced by 16.6% by using the attributes reduced by the proposed algorithm. Compared with the existing three element extraction algorithms (Genetic Algorithm (GA), Greedy Search Algorithm (GSA), and Attribute Reduction based on Conditional Entropy (ARCE) algorithm), the proposed algorithm has higher recall rate and low false positive rate. The experimental results show that the data set reduced by the proposed algorithm has better classification performance, which realizes an efficient extraction of network security situational elements.